#!/usr/bin/env python

"""
- Remember to change the above line to fit your environment
- Python >= 2.5 is required
"""

import covering

class Sigma:
    """
    Defines a (randomly generated) alphabet of random size between 'min' and 'max'
    """
    symbols = []
    size = 0

    def __init__(self, min = 10, max = 1000, symbols = None, size = None):
        if symbols is None:
            if size is None:
                import random
                random.seed()
                size = random.randint(min, max)

            self.symbols = range(1,size + 1)
            self.size = size
        else:
            self.symbols = symbols
            self.size = len(symbols)

    def __repr__(self):
        return ','.join([str(x) for x in self.symbols])

    def __len__(self):
        return len(self.symbols)

    def rcov(self, density = None, exact = False):
        import random
        import math
        if density is None or density > 0.5:
            random.seed()
            density = max(random.random(), 0.5)
        cover_size = int(math.ceil(len(self) * density))
        clique_size = int(math.ceil(1/density))
        
        blacklist, bucket, cover, tmp, last = [], [x for x in self.symbols], [], [], None
        random.shuffle(bucket)
        for i in range(1, cover_size):
            random.seed()
            tmp = random.sample(bucket, min(clique_size + int(random.random() * 2) - int(random.random()), len(bucket)))

            random.seed()
            for x in tmp:
                if x in bucket:
                    if random.random() > 0.5 or x in blacklist:
                        bucket.remove(x)
                        if x in blacklist:
                            blacklist.remove(x)
                else:
                    blacklist.append(x)

            cover.append(list(set(tmp)))

        second = [x for x in cover if len(x) > 0]
        third = []
        flat = set([])
        for x in second:
            ok = False
            for k in second:
                if k is not x:
                    if not set(k).issubset(set(x)):
                        ok = True
            if ok:
                third.append(x)

        for x in third:
            for z in x:
                flat.add(z)
        
        left = list(set(self.symbols) - flat)
        left_copy = [x for x in left]

        while len(left) > 0:
            for el in left_copy:
                random.seed()
                candidate = random.choice(range(0, len(third)-1))
                if el not in third[candidate]:
                    third[candidate].append(el)
                    left.remove(el)
            
        return covering.Covering(';'.join([','.join([str(y) for y in x]) for x in third]), self)

    def random_covering(self, density = None, exact = False, overlapping = None):
        import random
        if density is None:
            random.seed()
            density = random.random()
        wanted_size = int(len(self) * density)
        clique_size = int(1/density)
        if len(self) % clique_size is 0:
            is_int = True
        else:
            is_int = False
        
        first = [x for x in self.symbols]
        random.shuffle(first)

        second, third, tmp, first_copy = [], [], [], [x for x in first]
        n = 0
        lost = None

        for s in first_copy:
            tmp.append(s)
            if lost is not None:
                tmp.append(lost)
            first.remove(s)
            if n >= clique_size:
                random.seed()
                if random.random() > 0.5 and not exact:
                    lost = s
                else:
                    lost = None
                second.append([x for x in set(tmp)])
                tmp = []
                n = 0
            n += 1

        return covering.Covering(';'.join([','.join([str(y) for y in x]) for x in second]), self)

    def random_string(self, length = None, min = 10, max = 1000):
        import random
        string = []
        if length is None:
            length = random.randint(min, max)
        
        while len(string) < length:
            string.extend(random.sample(self.symbols, 1))
        
        return list(string)

def main():
    S = Sigma(size = 30)
    print 'Random alphabet:', S, 'of length', len(S)
    C = S.rcov(density = 0.3)
    print 'Dups:', [x for x in C.covering.keys() if len(C.covering[x]) > 1]
    print 'Leftout:', set([int(x) for x in S.symbols]) - set([int(x) for x in C.covering.keys()])
    print 'Random clique covering:', C, 'of size', len(C), 'and density', C.density
    U = S.random_string(50)
    print 'Random string:', U, 'of length', len(U)

"""
Invocation
"""
if __name__ == '__main__':
    main()
